package com.hjy.backend.versionManager;

import com.hjy.common.error.Error;

import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 维护了一个依赖等待图，以进行死锁检测
 */
public class LockTable {

    private Map<Long, List<Long>> x2u;  // 某个XID已经获得的资源的UID列表
    private Map<Long, Long> u2x;        // UID被某个XID持有(锁住了)
    private Map<Long, List<Long>> wait; // 正在等待UID的XID列表
    private Map<Long, Lock> waitLock;   // 正在等待资源的XID的锁
    private Map<Long, Long> waitU;      // XID正在等待的UID(锁住了)
    private Lock lock;

    public LockTable() {
        x2u = new HashMap<>();
        u2x = new HashMap<>();
        wait = new HashMap<>();
        waitLock = new HashMap<>();
        waitU = new HashMap<>();
        lock = new ReentrantLock();
    }

    /**
     * xid 对应的事务尝试使用某个 DataItem(uid)
     * 在每次出现等待的情况时，就尝试向图中增加一条边，并进行死锁检测。
     * <p>
     * 如果检测到死锁，就撤销这条边，不允许添加，并撤销该事务。
     * 不需要等待则返回null，否则返回锁对象
     * <p>
     * 会造成死锁则抛出异常
     * <p>
     * 如果需要等待的话，会返回一个上了锁的 Lock 对象
     *
     * @param xid 事务号
     * @param uid DataItem和Entry的唯一标识
     * @return 一个锁, 用于堵塞
     * @throws Exception
     */
    public Lock add(long xid, long uid) throws Exception {
        lock.lock();
        try {
            // dataItem 被xid对应的事务占有了, 无效操作
            if (isInList(x2u, xid, uid)) {
                return null;
            }
            // 如果这个 dataItem 没有被xid对应的事务占有
            if (!u2x.containsKey(uid)) {
                u2x.put(uid, xid);
                // 加入列表
                putIntoList(x2u, xid, uid);
                return null;
            }
            // 现在, xid对应的事务开始等待dataItem了
            waitU.put(xid, uid);
            //putIntoList(wait, xid, uid);
            putIntoList(wait, uid, xid);
            // 看看是否有死锁,
            if (hasDeadLock()) {
                // 有死锁, 就删边
                waitU.remove(xid);
                removeFromList(wait, uid, xid);
                throw Error.DeadlockException;
            }
            // 事务xid开始等待资源, 勿扰
            Lock l = new ReentrantLock();
            l.lock();
            waitLock.put(xid, l);
            return l;
        } finally {
            lock.unlock();
        }
    }

    /**
     * 在一个事务 commit 或者 abort(非法) 时，就可以释放所有它持有的锁，并将自身从等待图中删除
     *
     * @param xid
     */
    public void remove(long xid) {
        lock.lock();
        try {
            List<Long> l = x2u.get(xid);
            if (l != null) {
                while (l.size() > 0) {
                    Long uid = l.remove(0);
                    selectNewXID(uid);
                }
            }
            waitU.remove(xid);
            x2u.remove(xid);
            waitLock.remove(xid);
        } finally {
            lock.unlock();
        }
    }

    /**
     * 从等待队列中选择一个事务来占用uid
     *
     * @param uid 事务号
     */
    private void selectNewXID(long uid) {
        // 这个dataItem 已经自由了, 不被 xid 占有了
        u2x.remove(uid);
        // 赵到一个等待该dataItem的事务, 一个 dataItem 可能有多个事务在等待
        List<Long> l = wait.get(uid);
        if (l == null) return;
        assert l.size() > 0;

        while (l.size() > 0) {
            long xid = l.remove(0);
            if (!waitLock.containsKey(xid)) {
                continue;
            } else {
                // 很好, 这个dataItem 又不自由了
                u2x.put(uid, xid);
                // 事务xid获取到资源, 释放锁
                Lock lo = waitLock.remove(xid);
                waitU.remove(xid);
                lo.unlock();
                break;
            }
        }
        // 没有事务想用这个 dataItem , 不要你了
        if (l.size() == 0) wait.remove(uid);
    }

    private Map<Long, Integer> xidStamp; // 每个节点设置一个访问戳,初始化为 -1
    private int stamp;

    /**
     * 判断是否有死锁, 看有没有环, 跑一个 dfs 深搜
     * <p>
     * 查找图中是否有环的算法也非常简单，就是一个深搜，只是需要注意这个图不一定是连通图。
     * <p>
     * 思路就是为每个节点设置一个访问戳，都初始化为 -1(null)，随后遍历所有节点，以每个非 -1 的节点作为根进行深搜，
     * 并将深搜该连通图中遇到的所有节点都设置为同一个数字，不同的连通图数字不同。这样，如果在遍历某个图时，
     * 遇到了之前遍历过的节点，说明出现了环。
     *
     * @return
     */
    private boolean hasDeadLock() {
        xidStamp = new HashMap<>();
        stamp = 1; // 每个节点对应的访问戳不同
        // 对于每个不是 -1(null) 的节点, 我们都跑一个 dfs
        for (long xid : x2u.keySet()) {
            Integer s = xidStamp.get(xid);
            // 第一个取出来的是 null
            if (s != null && s > 0) {
                continue;
            }
            stamp++;
            if (dfs(xid)) {
                return true;
            }
        }
        return false;
    }

    private boolean dfs(long xid) {
        Integer stp = xidStamp.get(xid);
        // 这个点已经被遍历过,而且还一样, 我测, 死锁
        if (stp != null && stp == stamp) {
            return true;
        }
        if (stp != null && stp < stamp) {
            return false;
        }
        xidStamp.put(xid, stamp);
        // 获取下一个节点
        Long uid = waitU.get(xid);
        if (uid == null) return false;
        Long x = u2x.get(uid);
        assert x != null;
        return dfs(x);
    }

    /**
     * 将uid1删除 uid0对应的list中
     *
     * @param listMap map, 对应列表
     * @param uid0    uid0
     * @param uid1    uid1
     */
    private void removeFromList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        List<Long> l = listMap.get(uid0);
        if (l == null) return;
        Iterator<Long> i = l.iterator();
        while (i.hasNext()) {
            long e = i.next();
            if (e == uid1) {
                i.remove();
                break;
            }
        }
        if (l.size() == 0) {
            listMap.remove(uid0);
        }
    }

    /**
     * 将uid1加入 uid0对应的list中
     *
     * @param listMap map, 对应列表
     * @param uid0    uid0
     * @param uid1    uid1
     */
    private void putIntoList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        if (!listMap.containsKey(uid0)) {
            listMap.put(uid0, new ArrayList<>());
        }
        listMap.get(uid0).add(0, uid1);
    }

    /**
     * 判断 uid1 是否在 uid0 对应的列表中
     *
     * @param listMap map, 对应列表
     * @param uid0    uid0
     * @param uid1    uid1
     * @return
     */
    private boolean isInList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        List<Long> l = listMap.get(uid0);
        if (l == null) return false;
        Iterator<Long> i = l.iterator();
        while (i.hasNext()) {
            long e = i.next();
            if (e == uid1) {
                return true;
            }
        }
        return false;
    }

}
